import java.util.Comparator;
import java.util.PriorityQueue;

public class MaxSlidingWindow {
    // 滑动窗口的最大值
    // https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] != o2[1] ? o2[1] - o1[1] : o2[0] - o1[0];
            }
        });
        for (int i = 0; i < k; i++) {
            queue.offer(new int[]{i,nums[i]});
        }
        int[] ret = new int[nums.length-k+1];
        ret[0] = queue.peek()[1];
        for (int i = k; i < nums.length; i++) {
            while (!queue.isEmpty() && queue.peek()[0] <= i-k) {
                queue.poll();
            }
            queue.offer(new int[]{i,nums[i]});
            ret[i-k+1] = queue.peek()[1];
        }
        return ret;
    }

    public static void main(String[] args) {

    }
}
